package com.gitee.feizns.explore.data_structure.tree.cus.est;

import com.gitee.feizns.explore.data_structure.tree.cus.Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.function.BiConsumer;
import java.util.stream.Collectors;

/**
 * @author feizns
 * @since 2019/12/16
 */
public class EsT<K extends Comparable<K>, V> implements Tree<K, V> {

    public static void main(String[] args) {
        EsT esT = new EsT();
        esT.put(4, 1);
        esT.put(2, 1);
        esT.put(6, 1);
        esT.put(1, 1);
        esT.put(3, 1);
        esT.put(5, 1);
        esT.put(7, 1);
        esT.recursiveMiddleEach((k, v) -> System.out.println(k));

        System.out.println();
        esT.remove(7);
        esT.remove(7);

        esT.recursiveMiddleEach((k, v) -> System.out.println(k));
    }

    private Node<K, V> root;

    private int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public V get(Object key) {
        Node<K, V> node = node(root, (K) key);
        if ( node != null )
            for (Entry<K, V> entry : node.entries) {
                if ( entry.getKey().equals(key) )
                    return entry.getValue();
            }
        return null;
    }

    private Node<K, V> node(Node<K, V> node, K k) {
        if ( node != null ) {
            List<Entry<K, V>> entries = node.entries;
            int next = entries.size();
            for (int i = 0; i < entries.size(); i++) {
                int comp = k.compareTo(entries.get(i).getKey());
                if ( comp < 0 ) {
                    next = i;
                    break;
                } else if ( comp == 0 )
                    return node;
            }
            return node(node.node(next), k);
        }
        return null;
    }

    @Override
    public V put(K key, V value) {
        NAndV ret = put(root, key, value);
        root = ret.n;
        return ret.v;
    }

    private NAndV put(Node node, K k, V v) {
        if ( node == null ) {
            size++;
            return new NAndV(new Node(k, v), null, true);
        }

        List<Entry> entries = node.entries;
        int next = entries.size();
        for (int i = 0; i < node.size(); i++) {
            int comp = k.compareTo((K) entries.get(i).getKey());
            if ( comp < 0 ) {
                next = i;
                break;
            } else if ( comp == 0 ) {
                Entry e = entries.get(i);
                Object o = e.setValue(v);
                entries.set(i, e);
                return new NAndV(node, (V) o, false);
            }
        }

        Node nextNode = node.node(next);
        NAndV ret = put(nextNode, k, v);
        if ( nextNode != null && ret.merge ) {
            node.childNodes.set(next, null);
            Node newNode = merge(node, ret.n, next);
            if ( newNode.size() == 3 )
                return new NAndV(split(newNode), v, true);
            return new NAndV(newNode, v);
        }
        node.childNodes.set(next, ret.n);
        return new NAndV(node, v);
    }

    private Node<K, V> removeMerge(Node<K, V> original, Node<K, V> newNode) {
        int oSize = original.size();
        int nSize = newNode.size();
        Node originalLast = oSize == 2 ? original.node(2) : original.node(1);
        Node newNodeFirst = newNode.node(0);
        List<Entry<K, V>> newEntries = new ArrayList<>();
        List<Node<K,V>> newNodes = new ArrayList<>();
        if ( originalLast != null && newNodeFirst != null ) {
            original.childNodes.set(oSize, null);
            newNode.childNodes.set(0, null);
            if ( originalLast.size() == 1 && newNodeFirst.size() == 1 ) {
                Node merge = merge(originalLast, newNodeFirst, 1);
                newEntries.addAll(original.entries());
                newEntries.addAll(newNode.entries());
                original.childNodes.set(oSize, merge);
                newNodes.addAll(original.childNodes.subList(0, oSize + 1));
                newNodes.addAll(newNode.childNodes.subList(1, nSize + 1));
            } else if ( originalLast.size() == 2 || newNodeFirst.size() == 2 ) {
                Node node = removeMerge(originalLast, newNodeFirst);
                if ( node.size() == 1 ) {
                    newEntries.addAll(original.entries());
                    newEntries.add(node.entry(0));
                    newEntries.addAll(newNode.entries());
                    newNodes.addAll(original.childNodes.subList(0, oSize));
                    newNodes.addAll(node.nodes());
                    newNodes.addAll(newNode.childNodes.subList(1, nSize + 1));
                } else {
                    newEntries.addAll(original.entries());
                    newEntries.addAll(newNode.entries());
                    original.childNodes.set(oSize, node);
                    newNodes.addAll(original.childNodes.subList(0, oSize + 1));
                    newNodes.addAll(newNode.childNodes.subList(1, nSize + 1));
                }
            }
        } else {
            newEntries.addAll(original.entries());
            newEntries.addAll(newNode.entries());
            newNodes.addAll(original.childNodes.subList(0, oSize + 1));
            newNodes.addAll(newNode.childNodes.subList(1, nSize + 1));
        }

        Node<K, V> ret = new Node<K, V>(newEntries, newNodes);
        if ( ret.size() >= 3 )
            return split(ret);
        return ret;
    }

    private Node<K, V> merge(Node<K, V> original, Node<K, V> newNode, int newNodeIndex) {
        List<Entry> originalEntries = original.entries.stream().filter(Objects::nonNull).collect(Collectors.toList());
        List<Node<K, V>> originalNodes = original.childNodes;
        List<Entry<K, V>> newNodeEntries = newNode.entries.stream().filter(Objects::nonNull).collect(Collectors.toList());
        List<Node<K, V>> newNodeNodes = newNode.childNodes;
        originalEntries.addAll(newNodeIndex, newNodeEntries);
        originalNodes.addAll(newNodeIndex, newNodeNodes);
        List<Node<K, V>> nodes = new LinkedList<>();
        nodes.addAll(originalNodes.subList(0, 4));
        return new Node(originalEntries, nodes);
    }

    private Node<K, V> split(Node<K, V> node) {
        if ( node.size() == 4 ) {
            Node<K, V> root = new Node(node.entry(2));
            List<Entry> entries = new ArrayList<>(Arrays.asList(node.entry(0), node.entry(1)));
            List<Node> nodes = new ArrayList<>(node.childNodes.subList(0 , 3));
            Node<K, V> left = new Node(entries, nodes);
            Node<K, V> right = new Node(node.entry(3));
            right.childNodes.set(0, node.node(3));
            right.childNodes.set(1, node.node(4));
            root.childNodes.set(0, left);
            root.childNodes.set(1, right);
            return root;
        } else if ( node.size() == 3 ){
            Node<K, V> root = new Node(node.entry(1));
            Node<K, V> left = new Node(node.entry(0));
            left.childNodes.set(0, node.node(0));
            left.childNodes.set(1, node.node(1));
            Node<K, V> right = new Node(node.entry(2));
            right.childNodes.set(0, node.node(2));
            right.childNodes.set(1, node.node(3));
            root.childNodes.set(0, left);
            root.childNodes.set(1, right);
            return root;
        }
        return null;
    }

    //give up ..............
    @Override
    public V remove(Object key) {
//        NAndV nAndV = remove(root, null, (K) key);
//        root = nAndV.n;
//        return nAndV.v;
        return null;
    }

//    private NAndV remove(Node curt, Node parent, K k) {
//        if ( curt != null ) {
//            List<Entry> entries = curt.entries;
//            int next = entries.size();
//            for (int i = 0; i < entries.size(); i++) {
//                Entry<K, V> item = entries.get(i);
//                int comp = k.compareTo(item.getKey());
//                if ( comp < 0 ) {
//                    next = i;
//                    break;
//                } else if ( comp == 0 ) {
//                    V v = (V) curt.entry(i).getValue();
//                    int left = i - 1;
//                    int right = i + 1;
//                    Node leftNode = curt.node(left);
//                    Node rightNode = curt.node(right);
//                    if ( curt.isLeaf() ) {
//                        if ( curt.size() == 2 ) {
//                            curt.entries.remove(i);
//                        } else {
//                            if ( parent == null )
//                                curt = removeMerge(curt.node(0), curt.node(1));
//                            Node leftSibling;
//                            Node rightSibling;
//                            if ((leftSibling = leftSibling(parent, curt)) != null && leftSibling.size() == 2 )
//                                curt = rightRotate(parent, curt, leftNode);
//                            else if ((rightSibling = rightSibling(parent, curt)) != null && rightSibling.size() == 2 )
//                                curt = leftRotate(parent, curt, rightNode);
//                            else {
//                                if ( parent.size() == 2 ) {
//                                    if ( leftSibling != null ) {
//                                        int lef = parent.indexOf(leftSibling);
//                                        Entry pE = parent.entry(lef);
//                                        Node node = merge(leftSibling, new Node<K, V>(pE), 1);
//                                        parent.entries.remove(lef);
//                                        parent.childNodes.remove(lef);
//                                        parent.childNodes.set(lef, node);
//                                        curt = parent.node(lef + 1);
//                                    } else if ( rightSibling != null ) {
//                                        int rig = parent.indexOf(rightSibling);
//                                        Entry pE = parent.entry(rig - 1);
//                                        Node node = merge(new Node<K, V>(pE), rightSibling, 1);
//                                        parent.entries.remove(rig - 1);
//                                        parent.childNodes.remove(rig);
//                                        parent.childNodes.set(rig - 1, node);
//                                        curt = parent.node(rig - 1);
//                                    } else {
//                                        int of = parent.indexOf(curt);
//                                        if ( of == 0 ) {
//                                            Entry e = parent.entry(0);
//                                            curt.entries.set(0, e);
//                                            parent.entries.remove(0);
//                                            parent.childNodes.remove(0);
//                                        } else if ( of == 2 ) {
//                                            Entry e = parent.entry(1);
//                                            curt.entries.set(0, e);
//                                            parent.entries.remove(1);
//                                            parent.childNodes.remove(1);
//                                        }
//                                    }
//                                } else {
//                                    if ( leftSibling != null ) {
//                                        int lef = parent.indexOf(leftSibling);
//                                        Entry<K, V> pE = parent.entry(lef);
//                                        parent.childNodes.set(lef, null);
//                                        parent.childNodes.set(lef + 1, null);
//                                        NAndV nAndV = remove(root, null, pE.getKey());
//                                        root = nAndV.n;
//                                        curt = merge(leftSibling, new Node<K, V>(pE), 1);
//                                    } else if ( rightSibling != null ) {
//                                        int rig = parent.indexOf(rightSibling);
//                                        Entry<K, V> pE = parent.entry(rig - 1);
//                                        parent.childNodes.set(rig, null);
//                                        parent.childNodes.set(rig - 1, null);
//                                        NAndV nAndV = remove(root, null, pE.getKey());
//                                        root = nAndV.n;
//                                        curt = merge(new Node<K, V>(pE), rightSibling, 1);
//                                    }
//                                }
//                            }
//                        }
//                    } else {
//                        if ( leftNode != null ) {
//                            Entry<K, V> max = max(leftNode);
//                            curt.entries.set(i, new EntryImpl(max.getKey(), max.getValue()));
//                            NAndV nAndV = remove(leftNode, curt, max.getKey());
//                            curt.childNodes.set(left, nAndV.n);
//                        } else if ( rightNode != null ) {
//                            Entry<K, V> min = min(rightNode);
//                            curt.entries.set(i, new EntryImpl(min.getKey(), min.getValue()));
//                            NAndV nAndV = remove(rightNode, curt, min.getKey());
//                            curt.childNodes.set(right, nAndV.n);
//                        }
//                    }
//                    return new NAndV(curt, v);
//                }
//            }
//
//            Node nextNode = curt.node(next);
//            NAndV nAndV = remove(nextNode, curt, k);
//            curt.childNodes.set(next, nAndV.n);
//        }
//        return new NAndV(curt, null);
//    }

    private Node<K, V> rightRotate(Node<K, V> parent, Node<K, V> curt, Node<K, V> left) {
        int valIndex = parent.indexOf(left);
        Entry<K, V> entry = parent.entry(valIndex);
        List<Node<K, V>> leftNodes = left.nodes();
        Entry<K, V> leftLast = left.entries.get(left.entries.size() - 1);
        Node<K, V> leftLastNode = left.nodes().get(leftNodes.size() - 1);
        left.entries.remove(left.entries.size() - 1);
        left.childNodes.remove(leftNodes.size() - 1);
        curt.entries.set(0, new EntryImpl<>(entry.getKey(), entry.getValue()));
        curt.childNodes.add(0, leftLastNode);
        parent.entries.set(valIndex, new EntryImpl<>(leftLast.getKey(), leftLast.getValue()));
        return curt;
    }

    private Node<K, V> leftRotate(Node<K, V> parent, Node<K, V> curt, Node<K, V> right) {
        int valIndex = parent.indexOf(curt);
        Entry<K, V> entry = parent.entry(valIndex);
        List<Node<K, V>> rightNodes = right.nodes();
        Entry<K, V> rightFirst = right.entries.get(0);
        Node<K, V> rightFirstNode = rightNodes.remove(0);
        right.entries.remove(0);
        right.childNodes.remove(0);
        curt.entries.set(0, new EntryImpl<>(entry.getKey(), entry.getValue()));
        curt.childNodes.add(0, rightFirstNode);
        parent.entries.set(valIndex, new EntryImpl<>(rightFirst.getKey(), rightFirst.getValue()));
        return curt;
    }

    private Node<K, V> leftSibling(Node<K, V> parent, Node<K, V> curt) {
        return parent.node(parent.indexOf(curt) - 1);
    }

    private Node<K, V> rightSibling(Node<K, V> parent, Node<K, V> curt) {
        return parent.node(parent.indexOf(curt) + 1);
    }

    private Entry<K, V> min(Node node) {
        Node next = node.node(0);
        return next != null ? min(next) : node.entry(0);
    }

    private Entry<K, V> max(Node node) {
        Node next = node.node(node.size() - 1);
        return next != null ? max(next) : node.entry(node.size() - 1);
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    @Override
    public Set<K> keySet() {
        return null;
    }

    @Override
    public Collection<V> values() {
        return null;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }

    @Override
    public void recursiveBeforeEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void recursiveMiddleEach(BiConsumer<K, V> consumer) {
        recursiveMiddleEach(root, consumer);
    }

    private void recursiveMiddleEach(Node node, BiConsumer<K, V> consumer) {
        if ( node != null ) {
            List<Entry> list = node.entries;
            for (int i = 0; i < list.size(); i++) {
                recursiveMiddleEach(node.node(i), consumer);
                Entry<K, V> entry = list.get(i);
                consumer.accept(entry.getKey(), entry.getValue());
            }
            recursiveMiddleEach(node.node(list.size()), consumer);
        }
    }

    @Override
    public void recursiveAfterEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void recursiveSequenceTraversal(BiConsumer<K, V> consumer) {

    }

    @Override
    public void beforeEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void middleEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void afterEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void sequenceTraversal(BiConsumer<K, V> consumer) {

    }

    private class NAndV {

        boolean merge;

        Node n;

        V v;

        public NAndV(Node n, V v) {
            this.n = n;
            this.v = v;
        }

        public NAndV(Node n, V v, boolean merge) {
            this(n, v);
            this.merge = merge;
        }

    }

    private class Node<K extends Comparable<K>, V> {

        List<Entry<K, V>> entries = new LinkedList<>();

        List<Node<K, V>> childNodes = new LinkedList<>();

        {
            childNodes.add(null);
            childNodes.add(null);
            childNodes.add(null);
            childNodes.add(null);
        }

        public Node(K k, V v) {
            this(new EntryImpl(k, v));
        }

        public Node(Entry<K, V> entry) {
            entries.add(entry);
        }

        public Node(List<Entry<K, V>> entries, List<Node<K, V>> childNodes) {
            this.entries = entries;
            this.childNodes = childNodes;
        }

        public int size() {
            return entries.size();
        }

        public boolean isLeaf() {
            return childNodes.stream().allMatch(Objects::isNull);
        }

        public Entry<K, V> entry(int index) {
            return index >= 0 && index < entries.size() ? entries.get(index) : null;
        }

        public Node<K, V> node(int index) {
            return index >= 0 && index < childNodes.size() ? childNodes.get(index) : null;
        }

        public List<Node<K, V>> nodes() {
            return childNodes.stream().filter(Objects::nonNull).collect(Collectors.toList());
        }

        public int indexOf(Node<K, V> node) {
            return childNodes.indexOf(node);
        }

        public List<Entry<K, V>> entries() {
            return entries.stream().filter(Objects::nonNull).collect(Collectors.toList());
        }

    }

    private class EntryImpl<K extends Comparable<K>, V> implements Entry<K, V>, Comparable<EntryImpl<K, V>> {

        private K k;

        private V v;

        public EntryImpl(K k, V v) {
            this.k = k;
            this.v = v;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }

        @Override
        public V setValue(V value) {
            V oldV = v;
            v = value;
            return oldV;
        }

        @Override
        public int compareTo(EntryImpl<K, V> o) {
            return k.compareTo((K) o.k);
        }

    }

}
